package com.zhongnan.demo2;

public class Znkuaipai {
    public static void main(String[] args) {
        // 1.定义一个基准数
        // 2.从右边开始找比基准数小的
        // 3.从左边彩照比基准数大的
        // 4.直到左右重合
        // 5.基准数归位
        int[] arr = {6, 1, 4, 7, 3, 5, 8, 2, 10, 9};
        // Arrays.sort就是用快排实现的
        quiteSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    /**
     * 递归快排
     * @param arr
     * @param left
     * @param right
     */
    private static void quiteSort(int[] arr, int left, int right) {
        if(left> right) {
            return;
        }
        int leftNum = left;
        int rightNum = right;
        int num = arr[leftNum];
        while (left != right) {
            // 从右边开始寻找比基准数小的
            while (arr[right] >= num && right > left) {
                right--;
            }
            // 从左边开始找比基准数大的
            while (arr[left] <= num && right > left) {
                left++;
            }
            // 两者交换位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        // 基准数归位
        int temp = arr[left];
        arr[left] = arr[leftNum];
        arr[leftNum] = temp;
        // 左边的快排
        quiteSort(arr, leftNum, left - 1);
        // 右边的快排
        quiteSort(arr, left + 1, rightNum);
    }
    // 查找基准数的位置
    private static void quiteSort1(int[] arr, int left, int right) {
        int leftNum = left;
        int rightNum = right;
        int num = arr[leftNum];
        while (left != right) {
            // 从右边开始寻找比基准数小的
            while (arr[right] >= num && right > left) {
                right--;
            }
            // 从左边开始找比基准数大的
            while (arr[left] <= num && right > left) {
                left++;
            }
            // 两者交换位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        // 基准数归位
        int temp = arr[left];
        arr[left] = arr[leftNum];
        arr[leftNum] = temp;
    }
}
